package LRU缓存;

import java.util.*;

public class LRUCache {
    // 双向链表
    public class Node{
        int key;
        int value;
        Node prev;
        Node next;
        Node(){}
        Node(int key, int value){
            this.key = key;
            this.value = value;
        }
    }
    // 容量
    private int capacity;
    // 虚拟头节点
    // 用于标记双向链表的头部和尾部，使得在加入新节点和删除旧节点时更方便操作
    // 通过dummy节点将双向链表变成环形双向链表，dummy.next指向链表的头部，dummy.prev指向链表的尾部
    private Node dummy = new Node(0, 0);
    // 哈希表
    // 使用map的原因，get和put需要根据key，从map中查找和更新对应节点信息，并且以O(1)时间复杂度完成
    // map的另一个作用是避免加入重复的key到链表中去，可以对key进行去重
    private HashMap<Integer, Node> map = new HashMap<>();
    // 初始化
    public LRUCache(int capacity){
        this.capacity = capacity;
        dummy.next = dummy;
        dummy.prev = dummy;
    }
    // 获取
    public int get(int key){
        // 获取节点
        Node node = map.get(key);
        // 节点不存在
        if(node == null){
            return -1;
        }
        // 如果node存在，就将其移动到链表头部
        move2Head(node);
        return node.value;
    }
    // 插入
    public void put(int key, int value){
        // 获取节点
        Node node = map.get(key);
        // 节点存在
        if(node != null){
            // 不为null，就更新值并将其移动到头部
            node.value = value;
            move2Head(node);
        }else{
            // 为null，需要创建一个节点并添加到头部
            Node newNode = new Node(key, value);
            // 添加到哈希表
            map.put(key, newNode);
            // 添加到头部
            add2Head(newNode);
            // 超出容量
            if(map.size() > capacity){
                // 如果添加后超出容量，就把最后一个节点删除。因为哈希表中也要删除，这就是为什么删除函数要返回node的原因
                Node lastNode = removeTail();
                // 移除哈希表
                map.remove(lastNode.key);
            }
        }
    }
    // 添加到头部
    public void add2Head(Node node){
        // 将node插入到dummy节点后面
        dummy.next.prev = node;
        // 将node的next指向dummy的next
        node.next = dummy.next;
        // 将node的prev指向dummy
        node.prev = dummy;
        // 将dummy的next指向node
        dummy.next = node;
    }
    // 移除节点
    public void removeNode(Node node){
        // 将node的前一个节点的next指向node的next
        node.prev.next = node.next;
        // 将node的next节点的prev指向node的prev
        node.next.prev = node.prev;
    }
    // 移动到头部
    public void move2Head(Node node){
        // 将一个活跃节点移动到头部可分为两步：move2Head = removeNode + add2Head
        removeNode(node);
        add2Head(node);
    }
    // 移除尾部节点
    public Node removeTail(){
        // 获取尾部节点
        Node node = dummy.prev;
        // 移除节点
        removeNode(node);
        // 返回节点, 因为哈希表中也要删除，这就是为什么删除函数要返回node的原因
        return node;
    }
    public static void main(String[] args){
        // 初始化
        LRUCache lruCache = new LRUCache(2);
        // 插入
        lruCache.put(1, 1);
        lruCache.put(2, 2);
        // 获取
        System.out.println(lruCache.get(1));
        // 插入
        lruCache.put(3, 3);
        // 获取
        System.out.println(lruCache.get(2));
    }
}
